﻿using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public class ZhangChangPuCount : MonoBehaviour
{
	public int[] num;
    List<MyStruct<List<int>>> lsC = new List<MyStruct<List<int>>>();//符合要求的结果
    List<List<int>> lsCut = new List<List<int>>();//要剪的枝
    bool isCut = false;//是否是寻找剪枝的递归
    void OnGUI()
    {

        if (GUI.Button(new Rect(100, 0, 100, 100), "start"))
        {
            lsC.Clear();
            lsCut.Clear();
            Start();
        }

    }
    // Use this for initialization
    void Start () {
        if (num.Length < 3) return;
        List<int> lsNum = new List<int>(num);
        for (int i = 0; i < num.Length; i++)
            if (lsNum[i] == 0)
                lsNum[i] = Random.Range((int)1, (int)14);
        PrintList(lsNum);
        lsNum.Sort((d1, d2) => d2 - d1);
        isCut = true;
        for (int pickNum = 1; pickNum < lsNum.Count - 1; pickNum++)
            C_Pick(lsNum, pickNum);
        isCut = false;
        foreach (var a in lsCut)
        {
            List<int> lsNumCutted = new List<int>();
            lsNumCutted = RemoveSome(lsNum, a);//剪枝
            for (int i = 1; i <= (float)lsNumCutted.Count / 2; i++)
            {
                C_Pick(lsNumCutted, i);
            }
        }
        print(">>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>");
        GetResult();
    }
    //给一个数组,返回包含所有组合的可能情况,存在lsC里
    void C_Pick(List<int> lsNum, int pickNum)
    {
        C(lsNum, new List<int>(),pickNum);
    }
    //递归函数
    void C(List<int> ls, List<int> lsFinding,int pickNum, int from = 0, int depth = 0)
    {
        if (depth >= pickNum)
        {
            var lsG2 = (RemoveSome(ls, lsFinding));
            if (Count(lsFinding) == Count(lsG2))
                AddFinding(lsFinding, lsG2);
            if (isCut && (Count(lsG2)&1) == 0)
                lsCut.Add(lsFinding);
            return;
        }
        for (int i = from; i < ls.Count; i++)
        {
            List<int> lsFinding2 = new List<int>(lsFinding);
            lsFinding2.Add(ls[i]);
            C(ls, lsFinding2, pickNum, i + 1, depth + 1);
        }
    }
    List<int> RemoveSome(List<int> ls, List<int> lsRemove)
    {
        List<int> lsTemp = new List<int>(ls);
        foreach (var a in lsRemove) lsTemp.Remove(a);
        return lsTemp;
    }
    /// <summary>
    /// 求和
    /// </summary>
    /// <param name="ls"></param>
    /// <returns></returns>
    int Count(List<int> ls)
    {
        int o = 0;
        foreach (var a in ls) o += a;
        return o;
    }

    void GetResult()
    {
        foreach (var a in lsC)
            PrintList(a.group1, a.group2);
    }

    void AddFinding(List<int> ls1, List<int> ls2)
    {
        foreach(var a in lsC)
        {
            if ((ListEqual(a.group1, ls1) && ListEqual(a.group2, ls2)) || (ListEqual(a.group1, ls2) && ListEqual(a.group2, ls1)))//查重
                return;
        }
        MyStruct<List<int>> s = new MyStruct<List<int>>(ls1, ls2);
        lsC.Add(s);
    }

    bool ListEqual(List<int> ls1, List<int> ls2)
    {
        if (ls1.Count != ls2.Count) return false;
        ls1.Sort();
        ls2.Sort();
        bool isEqual = true;
        for (int i = 0; i < (ls1.Count<ls2.Count?ls1.Count:ls2.Count);i++)
        {
            if (ls1[i] != ls2[i])
                isEqual = false;
        }
        return isEqual;
    }

    void PrintList(List<int> ls)
    {
        string log = "";
        foreach (var v in ls)
        {
            log = log + v + " ";
        }
        print(log);
    }
    void PrintList(List<int> ls1, List<int> ls2)
    {
        string log = "";
        foreach (var v in ls1)
        {
            log = log + v + " ";
        }
        log = log + "/";
        foreach (var v in ls2)
        {
            log = log + v + " ";
        }
        log = log + ">>" + (ls1.Count + ls2.Count);
        print(log);
    }

    struct MyStruct<T>
    {
        public T group1;
        public T group2;
        public MyStruct(T g1, T g2)
        {
            group1 = g1;
            group2 = g2;
        }
    }
}
